//
// Created by YANHAI on 2020/7/15.
//

// 查找倒数第K个节点

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    explicit ListNode(int val) : val(val), next(nullptr) {}
};

/**
 * 主要注意判断head是否为空，k是否小于等于0
 * 以及链表长度小于k
 * @param head
 * @param k
 * @return
 */
ListNode *FindKthToTail(ListNode *head, unsigned int k) {
    if (head == nullptr || k == 0) {
        return nullptr;
    }
    ListNode *p1 = head;
    ListNode *p2 = head;
    int distance = 0;
    while (p2 != nullptr) {
        p2 = p2->next;
        // 当p2跑了k次后，p1开始跑，
        // p2跑到最后一个节点的下一个节点(p==null)时,p1此时指向的就是倒数第k个节点
        if (distance == k) {
            p1 = p1->next;
        } else {
            distance++;
        }
    }

    // 这里主要判断list的长度不足k个，则返回null
    return distance == k ? p1 : nullptr;
}

ListNode *createListNode(const string &str) {
    auto _head = new ListNode(0);;
    ListNode *last = _head;
    for (const auto &c : str) {
        auto p = new ListNode(c - '0');
        last->next = p;
        last = p;
    }
    ListNode *head = _head->next;
    delete _head;
    return head;
}

void freeListNode(ListNode *head) {
    while (head != nullptr) {
        ListNode *next = head->next;
        delete head;
        head = next;
    }
}

void printListNode(ListNode *head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

#define PRINT_NODE(x) do { \
    if (x) \
        std::cout << x->val << std::endl; \
    else \
        std::cout << "node is nullptr" << std::endl; \
} while(0)

int main() {
    auto head = createListNode("123456789");
    printListNode(head);

    auto p1 = FindKthToTail(head, 0);
    PRINT_NODE(p1);
    p1 = FindKthToTail(nullptr, 0);
    PRINT_NODE(p1);
    p1 = FindKthToTail(head, 20);
    PRINT_NODE(p1);
    p1 = FindKthToTail(head, 1);
    PRINT_NODE(p1);
    p1 = FindKthToTail(head, 7);
    PRINT_NODE(p1);

    freeListNode(head);
    return 0;
}
